#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdarg.h>
#include <time.h>
#include "loser_tree.h"

struct loser_tree {
	int	*internal_node;		// 内部节点
	int	nr_ex_node;		// 外部节点数量
	int	cap;			// 总容量
	getkey_t getkey;		// 获取败者树叶子节点的key
	cmpkey_t cmpkey;		// 比较叶子节点的key
};

#define HIST_NR		128
#define HIST_LEN	256

static char *lt_hist[HIST_NR];		//这个用来记录操作历史，调试目的
static int hist_ptr;

#define lt_log(fmt, ...)

//用来记录操作历史，用来定位bug
void _lt_log(char *fmt, ...)
{
	char *buf = lt_hist[hist_ptr];
	va_list ap;

	hist_ptr = (hist_ptr + 1) % HIST_NR;
	va_start(ap, fmt);
	vsnprintf(buf, HIST_LEN, fmt, ap);
	va_end(ap);
}

/* 输出败者树的结构信息 */
void lt_dump(struct loser_tree *lt)
{
	int i, n;

	fprintf(stderr, "loser_tree: nr=%d, cap=%d\n", lt->nr_ex_node, lt->cap);
	for (i = 0; i < lt->nr_ex_node; i++) {
		fprintf(stderr, "[%d]=%d ", i, lt->internal_node[i]);
		n = i+1;
		if (i == 0 || (n & (n-1)) == 0)
			fprintf(stderr, "\n");
	}
	fprintf(stderr, "\n");

	fprintf(stderr, "loser's tree operation's history\n");
	for (i = 0; i < HIST_NR; i++) {
		fprintf(stderr, "%d: %s", i, lt_hist[hist_ptr+i]);
	}
	fprintf(stderr, "\n");
}


/* 创建败者树 */
struct loser_tree *lt_create(int nr_ex_node, int cap, getkey_t getkey,
	cmpkey_t cmpkey)
{
	struct loser_tree *lt;
	int i;

	for (i=0; i<HIST_NR; i++) {
		lt_hist[i] = calloc(1, HIST_LEN);
		assert(lt_hist[i]);
	}

	lt = calloc(1, sizeof(*lt));
	assert(lt != NULL);

	lt->nr_ex_node = nr_ex_node;
	lt->cap = cap;
	lt->getkey = getkey;
	lt->cmpkey = cmpkey;
	lt->internal_node = calloc(1, cap * sizeof(int));
	assert(lt->internal_node);

	for (i = 0; i < lt->cap; i++)
		lt->internal_node[i] = INT_MAX;

	for (i = nr_ex_node-1; i >= 0; i--)
		lt_adjust(lt, i);

	lt_log("lt_create\n");
	return lt;
}

/* 获取内部节点, 调测代码 */
int *lt_get_ls(struct loser_tree *lt)
{
	return lt->internal_node;
}

/* 销毁败者树 */
void lt_destroy(struct loser_tree *lt)
{
	lt_log("lt_destroy\n");
	free(lt->internal_node);
	lt->cap = 0;
	lt->nr_ex_node = 0;
	free(lt);
}

static void swap(int *a, int *b)
{
	int tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;
}

/* 取走0号节点指向的叶节点之后，重新调整 */
void lt_adjust(struct loser_tree *lt, int _s)
{
	int s, t;
	void *key1, *key2;

	s = _s;
	t = (s + lt->nr_ex_node) / 2;
	while (t > 0) {
		lt->getkey(s, &key1);
		lt->getkey(lt->internal_node[t], &key2);
		if (lt->cmpkey(key1, key2) > 0) {
			swap(&s, &lt->internal_node[t]);
		}
		t /= 2;
	}
	lt->internal_node[0] = s;
}

/* 返回0号节点指向的叶节点 */
void lt_top(struct loser_tree *lt, int *index)
{
	*index = lt->internal_node[0];
}

/* 重新刷新所有叶子节点 */
void lt_refresh(struct loser_tree *lt, int nr_ex_node)
{
	int i;

	assert(nr_ex_node < lt->cap);

	for (i = 0; i <= nr_ex_node; i++)
		lt->internal_node[i] = INT_MAX;

	lt->nr_ex_node = nr_ex_node;
	for (i = lt->nr_ex_node-1; i >= 0; i--) {
		lt_adjust(lt, i);
	}
}



